• 先簡單回顧一下，今天預計分析的題目： 997. Find the Town Judge

• 題目連結：https://leetcode.com/problems/find-the-town-judge/

• 題目敘述：

  • 如果真的有法官，則法官會滿足這幾個條件：
    • 這位法官不會相信任何人。
    • 法官以外的所有人，都相信法官。
    • 整個小鎮只會恰有一個人滿足這些條件。
  • 給定鎮民之間的信任關係，要找出法官是誰。
  • 一個小鎮中有編號 1 ~ n 的人，謠傳這些人之中，有一個人是秘密的小鎮法官。
    

• 測資的 Input/Output

  • input 為 小鎮上有 n 個人 與 紀錄了信任關係的二維陣列 trust
  • output 需要回傳誰是小鎮的法官，若無則回傳 -1
    

• 若法官存在，則相信他者為 n - 1 人，而他相信者為 0 人

• 因此先用直接用迴圈掃過 trust ，紀錄每個人被相信與相信他人的數量

# 每個 Person 都紀錄會紀錄 [被別人相信的次數, 相信別人的次數]
person = [[0, 0] for i in range(n + 1)]

for i in trust:
    # 取得一比信任關係 (a 信任 b)
    a, b = i

    # a 信任他人的數量 + 1
    person[a][1] += 1

    # b 被信任的數量 + 1
    person[b][0] += 1

- 如圖，由於鎮民是由 1 開始編號，為了方便，我們開了 n + 1 長度的陣列用來記錄鎮民資料。
- 每個 person 的第零個欄位用來記錄被信任的次數，第一個欄位紀錄信任他人的次數。

• 再用一次迴圈掃過所有鎮民，找出符合法官條件者即可。

for i in range(1, n + 1):
    if person[i][1] == 0 and person[i][0] == n - 1:
        # 若第 i 位鎮民相信 0 人，且被 n - 1 人相信，則第 i 位就是法官
        return i

• 若無滿足條件者，則不存在法官。

return -1

• 完整程式碼如下

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
#                [BeTrustedNum, TrustOtherNum]
        person = [[0, 0] for i in range(n + 1)]

        for i in trust:
            a, b = i
#           有信任別人就加1
            person[a][1] += 1
#           有被人信任就加1
            person[b][0] += 1

        for i in range(1, n + 1):
#           滿足不信任其他人 和 被全部的人信任，則為法官
            if person[i][1] == 0 and person[i][0] == n - 1:
                return i

        return -1